// 该队列带头节点

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ElemType int

typedef struct LinkNode // 链式队列节点
{
    ElemType data;
    struct LinkNode *next;
} LinkNode;
typedef struct // 链式队列
{
    LinkNode *front, *rear; // 链式队列的头指针和尾指针
} LinkQueue;

void Init(LinkQueue *);
bool Is_empty(LinkQueue *);
void Enter(LinkQueue *, ElemType);    // 进队
void Traverse(LinkQueue *);           // 遍历队列输出
bool Delete(LinkQueue *, ElemType *); // 出队

int main()
{
    LinkQueue Q;
    ElemType val = 0;
    Init(&Q);
    Enter(&Q, 10);
    Enter(&Q, 9);
    Enter(&Q, 345);
    Traverse(&Q);
    if (Delete(&Q, &val))
        printf("Deleted successfully!The element is %d.\n", val);
    else
        printf("Failed to delete!The Queue is empty!\n");
    Traverse(&Q);
    return 0;
}

void Init(LinkQueue *pQ)
{
    pQ->front = (LinkNode *)malloc(sizeof(LinkNode));
    if (pQ->front == NULL)
    {
        printf("Dynamic memory allocation failed!\n");
        exit(-1);
    }
    pQ->rear = pQ->front;
    pQ->front->next = NULL;
    return;
}
bool Is_empty(LinkQueue *pQ)
{
    if (pQ->rear == pQ->front)
        return true;
    else
        return false;
}
void Enter(LinkQueue *pQ, ElemType val) // 进队
{
    pQ->rear->next = (LinkNode *)malloc(sizeof(LinkNode));
    if (pQ->rear->next == NULL)
    {
        printf("Dynamic memory allocation failed!\n");
        exit(-1);
    }
    pQ->rear = pQ->rear->next;
    pQ->rear->data = val;
    pQ->rear->next = NULL;
    return;
}
void Traverse(LinkQueue *pQ) // 遍历队列输出
{
    if (Is_empty(pQ))
    {
        printf("Failed to traverse!Queue is empty!\n");
        return;
    }
    LinkNode *temp = pQ->front->next;
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\nTraverse successfully!\n");
    return;
}
bool Delete(LinkQueue *pQ, ElemType *pVal) // 出队
{
    if (Is_empty(pQ))
        return false;
    *pVal = pQ->front->next->data;
    LinkNode *temp = pQ->front->next;
    pQ->front->next = pQ->front->next->next;
    if (pQ->rear == temp)
    {
        pQ->rear = pQ->front;
    }
    free(temp);
    temp = NULL;
    return true;
}